The present invention involves a data packet reordering system, and in particular a system for reordering digital spread spectrum (DSS) data packets using a reduced memory buffer.
In Direct-TV data protocol, program guides are sent as a collection of data packets. FIG. 1A shows a DSS transmitter 101 that transmits DSS data packets that are received by a DSS receiver 102 and routed to a SDRAM 103. The packets are stored in a random order.
FIG. 1B shows a typical SDRAM 103 with data packets (P0-P8) 105 stored at different locations 104, illustrated as L0-L8. FIG. 1B shows a first set of data packets 106 (packets P0-P4) stored at memory locations L4 to L8 respectively and a second set of data packets (P5-P8) 107 stored at memory locations L0 to L3 respectively.
However for efficient processing, the packets should be stored in the order illustrated in FIG. 1C, i.e. packet P0 should be stored in location L0, P1 in location L1 and so forth.
Currently a second memory buffer is used to reorder the data packets as they are received. FIG. 1D shows a second memory buffer 111 used for reordering data packets. When the first set 106 is received, in step S101, packets P0-P4 are moved to memory buffer 111. In step S102, data packets in second set 107 (P5-P8) are moved to the desired locations, L5-L8, as shown in FIG. 1C. Finally, in step S103, data packets in set 106 are moved to locations L0-L4. Currently, the reordering system is expensive and hence increases the overall system cost.
Therefore, what is needed is a system that can efficiently reorder incoming data packets without expensive memory buffer requirements.
The present invention addresses the foregoing by providing a method and system for reordering digital spread spectrum (DSS) data packets. The process locates the location (Ln) of a last data packet (Pn), and moves Pn to a memory buffer that can at least store a DSS data packet. Thereafter, the process locates a data packet (Px) stored at location Lx, wherein Px should be located at Ln. The process also determines if packet Pn should be located at location Lx, instead of Px. If Pn should not be located at Lx, the process moves Px to Ln.
If Pn should be located at Lx, the process locates the second last packet""s (Pnxe2x88x921) location (Lnxe2x88x921), and moves Pnxe2x88x921 to the memory buffer. Thereafter, the process locates a packet (Pxxe2x80x2) at location Lxxe2x80x2, that should be located at Lnxe2x88x921; and also determines if Pnxe2x88x921 should be located at Lxxe2x80x2. The process then moves Pxxe2x80x2 to Lnxe2x88x921 if Pnxe2x88x921 should not be located at location Lxxe2x80x2. The process is repeated until all the data packets have been reordered.
By virtue of the foregoing aspects of the present invention, a memory buffer that is smaller than conventional systems is required to reorder numerous data packets. Hence memory cost is reduced and that reduces the overall cost of the system. Furthermore, the present process is more efficient than the conventional prior art systems because data packets are only moved once, unlike conventional systems where data packets are moved more than once.